package gol;

import java.awt.Color;
import java.awt.Dimension;
import java.awt.Graphics;
import java.awt.Rectangle;
import java.awt.event.MouseAdapter;
import java.awt.event.MouseEvent;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.BitSet;
import java.util.LinkedList;
import java.util.Random;

import javax.swing.BorderFactory;
import javax.swing.JFrame;
import javax.swing.JPanel;
import javax.swing.border.BevelBorder;

/**
 * World model for a Game of Life simulation. The environment, and patterns
 * within them are modified with method calls
 * 
 * @author Jonathan Amery-Behr
 * 
 */

/**
 * @author Jonathan Amery-Behr
 *
 */
/**
 * @author Jonathan Amery-Behr
 *
 */
/**
 * @author Jonathan Amery-Behr
 * 
 */
/**
 * @author Jonathan Amery-Behr
 * 
 */
@SuppressWarnings("serial")
public class GameOfLife extends JPanel {

	public enum Cell {
		LIVE, DEAD, UNINHABITABLE
	};

	private static final int EXPANDAMOUNT = 4;
	// Number of cells to expand array by when
	// activity on edge. Should be even, >=2

	private static final int HISTORYLEN = 50;
	// Depth of histories to store

	protected static final int UNDOLEN = 25;
	// Depth of Undo history

	protected static final boolean ENABLEUNDO = true;
	protected static final boolean DEBUG = false;
	protected static final boolean HASHCHECK = true;
	// Sets whether to perform hash checks and maintai

	public boolean drawGrid = true;
	public boolean performUndo = true;

	boolean showGrid = true;

	boolean scrollable = false;
	int scrollFactor = 5; // Default Pixel threshold for introduction of
							// scrollbars

	// Stores for sequence histories
	ArrayList<Integer> cellCountHistory = new ArrayList<Integer>();
	ArrayList<Integer> widthHistory = new ArrayList<Integer>();
	ArrayList<Integer> heightHistory = new ArrayList<Integer>();
	ArrayList<Integer> areaHistory = new ArrayList<Integer>();
	ArrayList<Integer> netGrowthHistory = new ArrayList<Integer>();
	ArrayList<Integer> birthHistory = new ArrayList<Integer>();
	ArrayList<Integer> deathHistory = new ArrayList<Integer>();
	ArrayList<Boolean> xsymmetryHistory = new ArrayList<Boolean>();
	ArrayList<Boolean> ysymmetryHistory = new ArrayList<Boolean>();
	ArrayList<Boolean> symmetryHistory = new ArrayList<Boolean>();
	ArrayDeque<BitSet> gridHashHistory = new ArrayDeque<BitSet>();

	// Initial states for border behaviour
	boolean xtorus = false;
	boolean ytorus = false;
	boolean northExpand = true;
	boolean eastExpand = true;
	boolean southExpand = true;
	boolean westExpand = true;

	// Compensate for shifts in array resizing when zoomed.
	boolean fixedViewport = true;

	int rows;
	int columns;
	Cell[][] cellArray = new Cell[columns][rows];

	double cellWidth;
	double cellHeight;

	private LinkedList<Cell[][]> undoStates = new LinkedList<Cell[][]>();

	private String birth = "3";
	private String survival = "23";
	// Default ruleset, In this case Conway

	private int mouseButton;
	private Cell dragState;
	private JFrame frame;

	public int generations = 0;

	public GameOfLife(JFrame frame) {

		this.frame = frame;

		// Initialise cell array
		for (int i = 0; i < cellArray.length; i++) {
			for (int j = 0; j < cellArray[0].length; j++) {
				cellArray[i][j] = Cell.DEAD;
			}
		}

		setBorder(BorderFactory.createBevelBorder(BevelBorder.LOWERED));

		addMouseListener(new MouseAdapter() {
			@Override
			public void mousePressed(MouseEvent e) {
				clearHistories();

				mouseButton = e.getButton();
				int clickedCellColumn = (int) (((double) e.getX()) / getWidth() * columns);
				int clickedCellRow = (int) (((double) e.getY()) / getHeight() * rows);

				if (clickedCellColumn < 0 || clickedCellColumn >= columns
						|| clickedCellRow < 0 || clickedCellRow >= rows) {
					return;
				}
				if ((mouseButton == MouseEvent.BUTTON3 || e.isControlDown())
						&& (cellArray[clickedCellColumn][clickedCellRow] == Cell.UNINHABITABLE))
					dragState = Cell.UNINHABITABLE;
				else if (mouseButton == MouseEvent.BUTTON3 || e.isControlDown())
					dragState = Cell.DEAD;
				else if (mouseButton == MouseEvent.BUTTON1) {
					if (cellArray[clickedCellColumn][clickedCellRow] == Cell.UNINHABITABLE)
						dragState = Cell.LIVE;
					else
						dragState = cellArray[clickedCellColumn][clickedCellRow];
				}
			}

			public void mouseClicked(MouseEvent e) {
				int clickedCellColumn = (int) (((double) e.getX()) / getWidth() * columns);
				int clickedCellRow = (int) (((double) e.getY()) / getHeight() * rows);
				if (clickedCellColumn < 0 || clickedCellColumn >= columns
						|| clickedCellRow < 0 || clickedCellRow >= rows) {
					return;
				}

				if (mouseButton == MouseEvent.BUTTON1) {
					cellArray[clickedCellColumn][clickedCellRow] = toggleCell(cellArray[clickedCellColumn][clickedCellRow]);
				} else if (mouseButton == MouseEvent.BUTTON3
						|| e.isControlDown()) {
					if (cellArray[clickedCellColumn][clickedCellRow] == Cell.UNINHABITABLE)
						cellArray[clickedCellColumn][clickedCellRow] = Cell.DEAD;
					else
						cellArray[clickedCellColumn][clickedCellRow] = Cell.UNINHABITABLE;
				}
				repaint((int) (clickedCellColumn * cellWidth),
						(int) (clickedCellRow * cellHeight),
						(int) (cellWidth) + 1, (int) (cellHeight) + 1);
			}
		});

		addMouseMotionListener(new MouseAdapter() {
			private int previousColumn = -1;
			private int previousRow = -1;

			@Override
			public void mouseDragged(MouseEvent e) {

				if (mouseButton == MouseEvent.BUTTON2)
					return;

				int clickedCellColumn = (int) (((double) e.getX()) / getWidth() * columns);
				int clickedCellRow = (int) (((double) e.getY()) / getHeight() * rows);

				if (clickedCellColumn < 0 || clickedCellColumn >= columns
						|| clickedCellRow < 0 || clickedCellRow >= rows) {
					return;
				}
				if (mouseButton == MouseEvent.BUTTON3 || e.isControlDown()) {
					if (dragState == Cell.DEAD)
						cellArray[clickedCellColumn][clickedCellRow] = Cell.UNINHABITABLE;
					else if ((dragState == Cell.UNINHABITABLE)
							&& cellArray[clickedCellColumn][clickedCellRow] == Cell.UNINHABITABLE)
						cellArray[clickedCellColumn][clickedCellRow] = Cell.DEAD;
				} else if (mouseButton == MouseEvent.BUTTON1) {
					if (clickedCellColumn != previousColumn
							|| clickedCellRow != previousRow) {
						if (cellArray[clickedCellColumn][clickedCellRow] == Cell.UNINHABITABLE)
							cellArray[clickedCellColumn][clickedCellRow] = Cell.UNINHABITABLE;
						else
							cellArray[clickedCellColumn][clickedCellRow] = toggleCell(dragState);
					}
				}
				repaint((int) (clickedCellColumn * cellWidth),
						(int) (clickedCellRow * cellHeight),
						(int) (cellWidth) + 1, (int) (cellHeight) + 1);
				previousColumn = clickedCellColumn;
				previousRow = clickedCellRow;
			}
		});
	}

	private Cell toggleCell(Cell cell) {
		if (cell == Cell.LIVE)
			cell = Cell.DEAD;
		else if (cell == Cell.DEAD)
			cell = Cell.LIVE;
		else
			cell = Cell.UNINHABITABLE;
		return cell;
	}

	/**
	 * Resizes the internal grid model to the parameters whilst maintaining
	 * relative cell population Location. Resizing to a smaller grid will
	 * truncate at each edge *
	 * 
	 * @param newcolumns
	 *            width of new grid
	 * @param newrows
	 *            height of new grid
	 */
	public void setGridSize(int newcolumns, int newrows) {
		// clearHistories();
		if (!(newcolumns == columns) || !(newrows == rows)) {

			int pWidth = newcolumns * scrollFactor;
			int pHeight = newrows * scrollFactor;

			if (scrollable) {
				super.setPreferredSize(new Dimension(pWidth, pHeight));
				super.revalidate();
			} else
				super.setPreferredSize(new Dimension(0, 0));

			int xStart = 0, yStart = 0, xExtent = 0, yExtent = 0;
			xStart = (int) ((newcolumns - this.columns) / 2);
			xExtent = xStart + this.columns;
			yStart = (int) ((newrows - this.rows) / 2);
			yExtent = yStart + this.rows;

			int cCounter = 0;
			int rCounter = 0;

			Cell[][] tempArray = new Cell[newcolumns][newrows];

			for (int i = 0; i < tempArray.length; i++) {
				for (int j = 0; j < tempArray[0].length; j++) {
					tempArray[i][j] = Cell.DEAD;
				}
			}

			if (newcolumns >= this.columns) {

				for (int i = 0; i < newcolumns; i++) {
					if ((i < xStart) || (i >= xExtent))
						continue;

					for (int j = 0; j < newrows; j++) {
						if ((j < yStart) || (j >= yExtent))
							continue;

						tempArray[i][j] = cellArray[cCounter][rCounter++];
					}
					rCounter = 0;
					cCounter++;
				}
			} else {

				undoStates = new LinkedList<Cell[][]>();

				for (int i = 0; i < newcolumns; i++) {
					if ((i < xStart) || (i >= xExtent))
						continue;
					for (int j = 0; j < newrows; j++) {
						if ((j < yStart) || (j >= yExtent))
							continue;

						tempArray[cCounter][rCounter++] = cellArray[i - xStart][j
								- yStart];
					}
					rCounter = 0;
					cCounter++;

				}
			}

			this.columns = newcolumns;
			this.rows = newrows;
			cellArray = tempArray;
			repaint();
		}

		// nothing
	}

	/**
	 * Sets whether to scale the entire grid to the visible panel, or to
	 * introduce scrollbars to maintain the set scrollfactor zoom level
	 * 
	 * @param scrollable
	 *            state of whether grid is scrollable
	 */
	public void setScrollable(boolean scrollable) {
		this.scrollable = scrollable;

		// Define scaled panel dimensions
		int pWidth = columns * scrollFactor;
		int pHeight = rows * scrollFactor;

		if (scrollable) {
			super.setPreferredSize(new Dimension(pWidth, pHeight));
		} else
			super.setPreferredSize(new Dimension(0, 0));

		super.revalidate();

	}

	/**
	 * Changes ruleset used for cell evaluation
	 * 
	 * @param survivalConditions
	 *            A string containing each Survival rule as a single digit
	 *            value, non-numeric values are stripped
	 * @param birthConditions
	 *            A string containing each Survival rule as a single digit
	 *            value, non-numeric values are stripped
	 */
	public void setRules(String survivalConditions, String birthConditions) {

		this.birth = birthConditions.replaceAll("[^0-9.]", "");
		this.survival = survivalConditions.replaceAll("[^0-9.]", "");

	}

	/**
	 * Destroys the grid state, clearing all histories and related counters.
	 */
	public void killAllCells() {
		clearHistories();

		generations = 0;
		frame.setTitle("Game of Life Generations: " + 0);

		for (int column = 0; column < columns; column++) {
			for (int row = 0; row < rows; row++) {
				cellArray[column][row] = Cell.DEAD;
			}
		}
		repaint();
	}

	/**
	 * Clears each history store
	 */
	public void clearHistories() {
		netGrowthHistory.clear();
		birthHistory.clear();
		deathHistory.clear();
		widthHistory.clear();
		heightHistory.clear();
		areaHistory.clear();
		symmetryHistory.clear();
		xsymmetryHistory.clear();
		ysymmetryHistory.clear();
		cellCountHistory.clear();
		gridHashHistory.clear();

	}

	private boolean getBool(int column, int row) {
		if (cellArray[column][row] == Cell.LIVE)
			return true;
		else
			return false;
	}

	/**
	 * @return The grid state Cell array
	 */
	public Cell[][] getCellArray() {

		return cellArray;
	}

	/**
	 * @param cellStates
	 *            A new Cell array to overwrite the current. Grid will be
	 *            resized as necessary
	 */
	public void setCellArray(Cell[][] cellStates) {

		killAllCells();
		setGridSize(cellStates.length, cellStates[0].length);
		this.cellArray = cellStates;
		repaint();
	}

	public void paintComponent(Graphics g) {

		super.paintComponent(g);

		g.setColor(Color.LIGHT_GRAY);

		cellWidth = (double) super.getWidth() / columns;
		cellHeight = (double) super.getHeight() / rows;
		// no need to update so often maybe move to a resize
		// listener+setGridSize

		// Draw Grid Columns if showGrid is set
		if (showGrid) {
			for (int column = 0; column < columns; column++) {
				int cellX = (int) (cellWidth * column);
				g.drawLine(cellX, 0, cellX, getHeight());
			}
		}

		// Draw Grid Rows if showGrid is set
		if (showGrid) {
			for (int row = 0; row < rows; row++) {
				int cellY = (int) (cellHeight * row);
				g.drawLine(0, cellY, getWidth(), cellY);
			}
		}

		g.setColor(Color.BLUE);

		// Define pixel center of the panel
		int originx = (int) (cellWidth * (columns / 2));
		int originy = (int) (cellHeight * (rows / 2));

		// Draw the oddth Origin lines
		g.drawLine(originx, 0, originx, getHeight());
		g.drawLine(0, originy, getWidth(), originy);

		// If columns or rows is an even value, draw second grid line
		if ((columns & 1) == 1)
			g.drawLine(originx + (int) cellWidth, 0, originx + (int) cellWidth,
					getHeight());
		if ((rows & 1) == 1)
			g.drawLine(0, originy + (int) cellHeight, getWidth(), originy
					+ (int) cellHeight);

		g.setColor(Color.DARK_GRAY);

		for (int column = 0; column < columns; column++) {
			for (int row = 0; row < rows; row++) {

				int cellX = (int) (cellWidth * column);
				int cellY = (int) (cellHeight * row);

				int thisCellWidth = (int) (cellWidth * (column + 1) - cellX);
				int thisCellHeight = (int) (cellHeight * (row + 1) - cellY);

				if (cellArray[column][row] == Cell.LIVE) {
					if (showGrid) {
						g.fillRect(cellX + 1, cellY + 1, thisCellWidth - 1,
								thisCellHeight - 1);
					} else {
						g.fillRect(cellX, cellY, Math.max(thisCellWidth, 1),
								Math.max(thisCellHeight, 1));
					}
				} else if (cellArray[column][row] == Cell.UNINHABITABLE) {
					g.setColor(Color.red);

					if (showGrid) {
						g.fillRect(cellX + 1, cellY + 1, thisCellWidth - 1,
								thisCellHeight - 1);
					} else {
						g.fillRect(cellX, cellY, Math.max(thisCellWidth, 1),
								Math.max(thisCellHeight, 1));
					}
					g.setColor(Color.DARK_GRAY);
				}
			}
		}
	}

	/**
	 * @return Growth history formatted as a comma delimited string
	 */
	public String getNetGrowthHistory() {

		if (netGrowthHistory.isEmpty())
			return "";

		String str = "";
		boolean trivial = true;

		int last = netGrowthHistory.get(0);
		for (int i : netGrowthHistory) {
			if (last != i) {
				trivial = false;
				break;
			}
			last = i;
		}
		if (trivial)
			return "";

		for (Integer i : netGrowthHistory) {
			str = str + i + ",";
		}
		return str;
	}

	/**
	 * @return Birth history formatted as a comma delimited string
	 */
	public String getBirthHistory() {

		if (birthHistory.isEmpty())
			return "";

		String str = "";
		boolean trivial = true;

		int last = birthHistory.get(0);
		for (int i : birthHistory) {
			if (last != i) {
				trivial = false;
				break;
			}
			last = i;
		}
		if (trivial)
			return "";
		for (Integer i : birthHistory) {
			str = str + i + ",";
		}
		return str;
	}

	/**
	 * @return Death history formatted as a comma delimited string
	 */
	public String getDeathHistory() {

		if (deathHistory.isEmpty())
			return "";

		String str = "";
		boolean trivial = true;

		int last = deathHistory.get(0);
		for (int i : deathHistory) {
			if (last != i) {
				trivial = false;
				break;
			}
			last = i;
		}
		if (trivial)
			return "";
		for (Integer i : deathHistory) {
			str = str + i + ",";
		}
		return str;
	}

	/**
	 * @return Cell Population history formatted as a comma delimited string
	 */
	public String getCellCountHistory() {

		if (cellCountHistory.isEmpty())
			return "";

		String str = "";
		boolean trivial = true;

		int last = cellCountHistory.get(0);
		for (int i : cellCountHistory) {
			if (last != i) {
				trivial = false;
				break;
			}
			last = i;
		}
		if (trivial)
			return "";
		for (Integer i : cellCountHistory) {
			str = str + i + ",";
		}
		return str;
	}

	/**
	 * @return Population Width history formatted as a comma delimited string
	 */
	public String getWidthHistory() {

		if (widthHistory.isEmpty())
			return "";

		String str = "";
		boolean trivial = true;

		int last = widthHistory.get(0);
		for (int i : widthHistory) {
			if (last != i) {
				trivial = false;
				break;
			}
			last = i;
		}
		if (trivial)
			return "";
		for (Integer i : widthHistory) {
			str = str + i + ",";
		}
		return str;
	}

	/**
	 * @return Population Height history formatted as a comma delimited string
	 */
	public String getHeightHistory() {

		if (heightHistory.isEmpty())
			return "";

		String str = "";
		boolean trivial = true;

		int last = heightHistory.get(0);
		for (int i : heightHistory) {
			if (last != i) {
				trivial = false;
				break;
			}
			last = i;
		}
		if (trivial)
			return "";
		for (Integer i : heightHistory) {
			str = str + i + ",";
		}
		return str;
	}

	/**
	 * @return Population Area history formatted as a comma delimited string
	 */
	public String getAreaHistory() {

		if (areaHistory.isEmpty())
			return "";

		String str = "";
		boolean trivial = true;

		int last = areaHistory.get(0);
		for (int i : areaHistory) {
			if (last != i) {
				trivial = false;
				break;
			}
			last = i;
		}
		if (trivial)
			return "";
		for (Integer i : areaHistory) {
			str = str + i + ",";
		}
		return str;
	}

	/**
	 * @return Binary sequence of x or y symmetry as a comma delimited string
	 */
	public String getSymmetryHistory() {

		if (symmetryHistory.isEmpty())
			return "";

		String str = "";
		boolean trivial = true;

		Boolean last = symmetryHistory.get(0);
		for (Boolean i : symmetryHistory) {
			if (last != i) {
				trivial = false;
				break;
			}
			last = i;
		}
		if (trivial)
			return "";
		for (Boolean i : symmetryHistory) {
			if (i)
				str = str + "1,";
			else
				str = str + "0,";
		}
		return str;
	}

	/**
	 * @return Binary sequence of x symmetry as a comma delimited string
	 */
	public String getXSymmetryHistory() {

		if (xsymmetryHistory.isEmpty())
			return "";

		String str = "";
		boolean trivial = true;

		Boolean last = xsymmetryHistory.get(0);
		for (Boolean i : xsymmetryHistory) {
			if (last != i) {
				trivial = false;
				break;
			}
			last = i;
		}
		if (trivial)
			return "";
		for (Boolean i : xsymmetryHistory) {
			if (i)
				str = str + "1,";
			else
				str = str + "0,";
		}
		return str;

	}

	/**
	 * @return Binary sequence of y symmetry as a comma delimited string
	 */
	public String getYSymmetryHistory() {

		if (ysymmetryHistory.isEmpty())
			return "";

		String str = "";
		boolean trivial = true;

		Boolean last = ysymmetryHistory.get(0);
		for (Boolean i : ysymmetryHistory) {
			if (last != i) {
				trivial = false;
				break;
			}
			last = i;
		}
		if (trivial)
			return "";
		for (Boolean i : ysymmetryHistory) {
			if (i)
				str = str + "1,";
			else
				str = str + "0,";
		}
		return str;
	}

	/**
	 * attempts to Revert a single generation back in undoHistory updating all
	 * histories and counters
	 */
	public void undoGeneration() {
		if (undoStates.size() > 0) {

			Cell[][] cellStates = undoStates.removeFirst();

			for (int column = 0; column < columns; column++) {
				for (int row = 0; row < rows; row++) {
					cellArray[column][row] = Cell.DEAD;
				}
			}

			this.columns = cellStates.length;
			this.rows = cellStates[0].length;

			this.cellArray = cellStates;
			repaint();

			popHistories();

			frame.setTitle("Game of Life Generations: " + --generations);
		} else
			System.out.println("No more states to undo!");
	}

	private void popHistories() {

		if (cellCountHistory.size() > 0)
			cellCountHistory.remove(cellCountHistory.size() - 1);
		if (netGrowthHistory.size() > 0)
			netGrowthHistory.remove(netGrowthHistory.size() - 1);
		if (birthHistory.size() > 0)
			birthHistory.remove(birthHistory.size() - 1);
		if (deathHistory.size() > 0)
			deathHistory.remove(deathHistory.size() - 1);
		if (areaHistory.size() > 0)
			areaHistory.remove(areaHistory.size() - 1);
		if (symmetryHistory.size() > 0)
			symmetryHistory.remove(symmetryHistory.size() - 1);
		if (xsymmetryHistory.size() > 0)
			xsymmetryHistory.remove(xsymmetryHistory.size() - 1);
		if (ysymmetryHistory.size() > 0)
			ysymmetryHistory.remove(ysymmetryHistory.size() - 1);
		if (gridHashHistory.size() > 0)
			gridHashHistory.removeFirst();
	}

	// Declare boundaries for the two bounding boxes, one for minimum draw area,
	// and one for capturing all life
	int leftBoundDraw, rightBoundDraw, topBoundDraw, botBoundDraw;
	int leftBoundLife, rightBoundLife, topBoundLife, botBoundLife;

	private boolean growEastNextTick = false;
	private boolean growWestNextTick = false;
	private boolean growNorthNextTick = false;
	private boolean growSouthNextTick = false;
	private int birthCounter, deathCounter, cellCounter;

	/**
	 * Evaluate a single generation, Updating histories and drawing result to
	 * the grid panel.
	 */
	public void doGeneration() {
		birthCounter = 0;
		deathCounter = 0;
		cellCounter = 0;

		frame.setTitle("Game of Life Generations: " + ++generations);

		expandGrid();

		if (ENABLEUNDO && performUndo) {
			undoStates.addFirst(cellArray.clone());

			if (undoStates.size() > UNDOLEN)
				undoStates.removeLast();
		}

		// Set bounding areas to a minumum
		leftBoundDraw = columns;
		rightBoundDraw = 0;
		topBoundDraw = rows;
		botBoundDraw = 0;
		leftBoundLife = columns;
		rightBoundLife = 0;
		topBoundLife = rows;
		botBoundLife = 0;

		Cell[][] sucArray = new Cell[columns][rows];
		boolean[][] visited = new boolean[columns][rows];

		for (int column = 0; column < columns; column++) {
			for (int row = 0; row < rows; row++) {

				if (getBool(column, row)) { // For each live cell
					cellCounter++;

					// Trigger resize if close to border
					if (column + 2 >= columns)
						growEastNextTick = true;
					if (column - 1 <= 0)
						growWestNextTick = true;
					if (row + 2 >= rows)
						growSouthNextTick = true;
					if (row - 1 <= 0)
						growNorthNextTick = true;

					int origColumn = column;
					int origRow = row;

					for (int c = -1; c <= 1; c++) {
						for (int r = -1; r <= 1; r++) {
							row = origRow;
							column = origColumn;
							if (xtorus) { // IF x torus
								if ((column + c > columns - 1)) {
									column = -1;
								}
								if (column + c < 0) {
									column = columns;
								}
							}

							else { // Else its a wall
								if (!eastExpand && (column + c > columns - 1)) {
									continue;
								}
								if (!westExpand && (column + c < 0))
									continue;
							}
							if (ytorus) {// IF y torus
								if (row + r > rows - 1) {
									row = -1;
								}
								if (row + r < 0) {
									row = rows;
								}
							} else {// Else its a wall

								if (!southExpand && (row + r > row - 1)) {
									continue;
								}
								if (!northExpand && (row + r < 0)) {
									continue;
								}
							}

							if (!visited[column + c][row + r]) {
								int neighborCount = countNeighbors(column + c,
										row + r);
								visited[column + c][row + r] = true;
								sucArray[column + c][row + r] = nextState(
										cellArray[column + c][row + r],
										neighborCount);
							}
							row = origRow;
							column = origColumn;
						}
					}
					if (column < leftBoundLife)
						leftBoundLife = column;
					if (column >= rightBoundLife)
						rightBoundLife = column + 1;
					if (row < topBoundLife)
						topBoundLife = row;
					if (row > botBoundLife)
						botBoundLife = row + 1;
				}
				int neighborCount = countNeighbors(column, row);

				Cell sucState = nextState(cellArray[column][row], neighborCount);
				sucArray[column][row] = sucState;

				if (cellArray[column][row] != sucState) {
					if (sucState == Cell.LIVE) {
						birthCounter++;
					} else
						deathCounter++;

					if (column < leftBoundDraw)
						leftBoundDraw = column;
					if (column >= rightBoundDraw)
						rightBoundDraw = column + 1;
					if (row < topBoundDraw)
						topBoundDraw = row;
					if (row > botBoundDraw)
						botBoundDraw = row + 1;
				}
			}
		}

		cellArray = sucArray;

		if ((leftBoundDraw == columns) && (rightBoundDraw == 0)
				&& (topBoundDraw == rows) && (botBoundDraw == 0)) {
			// Do nothing if there is no change
		} else {

			pushHistories();

			int repaintX = (int) ((leftBoundDraw) * cellWidth);
			int repaintY = (int) ((topBoundDraw) * cellHeight);
			int repaintW = (int) ((1 + rightBoundDraw - leftBoundDraw) * (cellWidth + 1));
			int repaintH = (int) ((1 + botBoundDraw - topBoundDraw) * (cellHeight + 1));
			if (drawGrid)
				repaint(repaintX, repaintY, repaintW, repaintH);
		}

	}

	/**
	 * @return whether the grid is symmetrical over Y
	 */
	private boolean testYSymmetry() {

		for (int r = 0; r < rows; r++) {
			for (int c = 0; c < columns / 2; c++) {
				if ((cellArray[c][r]) != (cellArray[columns - 1 - c][r]))
					return false;
			}
		}
		return true;
	}

	/**
	 * @return whether the grid is symmetrical over X
	 */
	private boolean testXSymmetry() {
		for (int c = 0; c < columns; c++) {
			for (int r = 0; r < (int) (rows / 2d); r++) {
				if ((cellArray[c][r]) != (cellArray[c][rows - 1 - r]))
					return false;
			}
		}
		return true;
	}

	/**
	 * Adds a single generation to each history store
	 */
	private void pushHistories() {

		if (cellCountHistory.size() == HISTORYLEN)
			cellCountHistory.remove(0);
		cellCountHistory.add(cellCounter);

		if (netGrowthHistory.size() == HISTORYLEN)
			netGrowthHistory.remove(0);
		netGrowthHistory.add(birthCounter - deathCounter);

		if (birthHistory.size() == HISTORYLEN)
			birthHistory.remove(0);
		birthHistory.add(birthCounter);

		if (deathHistory.size() == HISTORYLEN)
			deathHistory.remove(0);
		deathHistory.add(deathCounter);

		if (widthHistory.size() == HISTORYLEN)
			widthHistory.remove(0);
		widthHistory.add((rightBoundLife - leftBoundLife));

		if (heightHistory.size() == HISTORYLEN)
			heightHistory.remove(0);
		heightHistory.add((botBoundLife - topBoundLife));

		if (areaHistory.size() == HISTORYLEN)
			areaHistory.remove(0);
		areaHistory.add((rightBoundLife - leftBoundLife)
				* (botBoundLife - topBoundLife));

		if (xsymmetryHistory.size() == HISTORYLEN)
			xsymmetryHistory.remove(0);
		xsymmetryHistory.add(testXSymmetry());// TODO
		if (ysymmetryHistory.size() == HISTORYLEN)
			ysymmetryHistory.remove(0);
		ysymmetryHistory.add(testYSymmetry());// TODO

		if (symmetryHistory.size() == HISTORYLEN)
			symmetryHistory.remove(0);
		symmetryHistory.add(testXSymmetry() || testYSymmetry());// TODO

		if (DEBUG) {
			System.out.println("C/" + cellCounter + "\tG/"
					+ (birthCounter - deathCounter) + "\tB/" + birthCounter
					+ "\tD/" + deathCounter + "\tW/"
					+ (rightBoundLife - leftBoundLife) + "\tH/"
					+ (botBoundLife - topBoundLife) + "\tX/" + testXSymmetry()
					+ "\tY/" + testYSymmetry());
		}

	}

	/**
	 * Calculate a hash of the current grid state, compare it to the hash
	 * history
	 * 
	 * @return the location in the history, if it is found, else 0
	 */
	public int hashCheck() {
		if (!HASHCHECK || !xtorus || !ytorus)
			return 0;
		BitSet hash = hashGrid();
		int i = 0;

		for (BitSet oldhash : gridHashHistory) {
			i++;
			if (oldhash.equals(hash)) {

				gridHashHistory.clear();
				gridHashHistory.addFirst(hash);
				if (i == 1)
					i++;
				return i;
			}
		}

		gridHashHistory.addFirst(hash);
		return 0;
	}

	private BitSet hashGrid() {
		BitSet bs = new BitSet(columns * rows);
		int i = 0;
		for (Cell[] column : cellArray) {
			for (Cell cell : column) {
				if (cell == Cell.LIVE)
					bs.set(i);
				// else bs.set(i, false);
				i++;
			}
		}

		// long h = 1234;
		// long[] words = bs.toLongArray();
		// for (i = words.length; --i >= 0; )
		// h ^= words[i] * (i + 1);
		// return (int)((h >> 32) ^ h);

		return bs;
	}

	/**
	 * Resizes the grid model if set to do so
	 */
	private void expandGrid() {

		if (!xtorus && eastExpand && growEastNextTick) {
			setGridSize(columns + EXPANDAMOUNT, rows);
			growEastNextTick = false;
			if (fixedViewport)
				super.scrollRectToVisible(new Rectangle((int) (getVisibleRect()
						.getMaxX() + scrollFactor * EXPANDAMOUNT / 2 - 1),
						(int) (getVisibleRect().getCenterY()), 1, 1));

		} else if (!xtorus && westExpand && growWestNextTick) {
			setGridSize(columns + EXPANDAMOUNT, rows);
			growWestNextTick = false;
			if (fixedViewport)
				super.scrollRectToVisible(new Rectangle((int) (getVisibleRect()
						.getMaxX() + scrollFactor * EXPANDAMOUNT / 2 - 1),
						(int) (getVisibleRect().getCenterY()), 1, 1));

		}
		if (!ytorus && northExpand && growNorthNextTick) {
			setGridSize(columns, rows + EXPANDAMOUNT);
			growNorthNextTick = false;
			if (fixedViewport)
				super.scrollRectToVisible(new Rectangle((int) (getVisibleRect()
						.getCenterX()), (int) (getVisibleRect().getMaxY()
						+ scrollFactor * EXPANDAMOUNT / 2 - 1), 1, 1));

		} else if (!ytorus && southExpand && growSouthNextTick) {
			setGridSize(columns, rows + EXPANDAMOUNT);
			growSouthNextTick = false;
			if (fixedViewport)
				super.scrollRectToVisible(new Rectangle((int) (getVisibleRect()
						.getCenterX()), (int) (getVisibleRect().getMaxY()
						+ scrollFactor * EXPANDAMOUNT / 2 - 1), 1, 1));

		}
	}

	/**
	 * Determines the new state of a cell.
	 * 
	 * @param cellState
	 *            The current state of the prospective cell
	 * @param neighborCount
	 *            The number of live neighbours that cell has
	 * @return The new cell state made with respect to the the neighbour count
	 */
	private Cell nextState(Cell cellState, int neighborCount) {

		if (cellState == Cell.UNINHABITABLE)
			return cellState;

		if (cellState == Cell.DEAD) {
			for (int i = 0; i < birth.length(); i++) {
				if (neighborCount == (birth.charAt(i) - 48))
					return Cell.LIVE;
			}
		}

		if (cellState == Cell.LIVE) {
			for (int i = 0; i < survival.length(); i++) {
				if (neighborCount == (survival.charAt(i) - 48))
					return Cell.LIVE;
			}
		}
		return Cell.DEAD;
	}

	/**
	 * @param column
	 *            Column coordinate of a particular cell
	 * @param row
	 *            Row coordinate of a particular cell
	 * @return the number of live neighbours that cell has with respect to the
	 *         grid state
	 */
	private int countNeighbors(int column, int row) {
		int origColumn = column;
		int origRow = row;
		int neighborCount = 0;

		for (int c = -1; c <= 1; c++) {
			column = origColumn;

			if (xtorus) { // if torus on x
				if (column + c > columns - 1) {
					column = -1;
				}
				if (column + c < 0) {
					column = columns;
				}
			} else {

				if (column + c < 0) { // else left wall
					continue;
				} else if (column + c > columns - 1) { // else right wall
					continue;
				}
			}

			for (int r = -1; r <= 1; r++) {
				row = origRow;

				// don't count yourself
				if (c == 0 && r == 0) {
					continue;
				}

				if (ytorus) { // If torus on y
					if (row + r > rows - 1) {
						row = -1;
					}
					if (row + r < 0) {
						row = rows;
					}
				} else {
					if (row + r < 0) { // else top wall
						continue;
					}
					if (row + r > rows - 1) { // else bottom wall
						continue;
					}
				}
				if (getBool(column + c, row + r)) {
					neighborCount++;
				}
			}
		}
		return neighborCount;
	}

	public void setScrollFactor(int d) {
		scrollFactor = d;
		setScrollable(true);
	}

	public boolean isEmpty() {

		for (Cell[] col : cellArray) {
			for (Cell cell : col) {
				if (cell == Cell.LIVE)
					return false;
			}
		}

		return true;
	}

}
